package zisu.algorithm.algorithm.MaxHeap.priorityQueue;

//给定一个非空的整数数组，返回其中出现频率前 k 高的元素。


import java.util.*;
import java.util.PriorityQueue;

/**
 * 实例1
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 */



public class LeetCode347 {
    private class Freq implements Comparable<Freq>{
        private int e,freq;

        public Freq(int e,int freq){
            this.e = e;
            this.freq = freq;
        }


        @Override
        public int compareTo(Freq another) {
            // 最小堆（新来的比我大 返回-1 ，，以我为本体，比我大返回-1 比我小返回1），，最大堆和这个相反
            if(this.e < another.e){
                return -1;
            }else if(this.e > another.e){
                return 1;
            }else {
                return 0;
            }
        }
    }

    //因为java只提供最小堆，所以需要一个比较器 (Comparator 比较器)
    private class FreqComparator implements Comparator<Freq>{

        @Override
        public int compare(Freq o1, Freq o2) {
            //这里的判断逻辑和 上面compareTo判断逻辑是一样的
            return o1.freq - o2.freq;
        }
    }

    // num这个数组是输入的 源数据
    public List<Integer> topKFrequent(int[] nums, int k) throws Exception {
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for(int num:nums){
            if(map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else {
                map.put(num,1);
            }
        }

        // java.util 默认的是最小堆
        PriorityQueue<Freq> freqPriorityQueue = new PriorityQueue<>();

        // 用比较器来 比较Freq的谁优先级大 谁的优先级小。 定义自己的字符串比较器。
        PriorityQueue<Freq> freqPriorityQueue2 = new PriorityQueue<>(new FreqComparator());


        // map.keySet() 是 K(键) 的集合
        for (int i : map.keySet()){ 
            if(freqPriorityQueue.size() < k){
                freqPriorityQueue.add(new Freq(i,map.get(i)));
            }else if(freqPriorityQueue.peek().freq < map.get(i)){
                Freq freq = freqPriorityQueue.remove();
                freqPriorityQueue.add(new Freq(i,map.get(i)));
            }
        }
        LinkedList<Integer> linkedList = new LinkedList<>();
        while (!freqPriorityQueue.isEmpty()){
            linkedList.add(freqPriorityQueue.remove().e);
        }
        return linkedList;
    }
}